from math import sqrt

def stream_ngram(n, list):
  result = []
  for pos in xrange(len(list) - n + 1):
    result.append(list[pos:pos+n])
  return result

def ubgrams(list):
  return sum([stream_ngram(n,list) for n in xrange(1,3)],[])
def ubtgrams(list):
  return sum([stream_ngram(n,list) for n in xrange(1,4)],[])
def bttgrams(list):
  return sum([stream_ngram(n,list) for n in xrange(2,5)],[])

def frequencies(token_stream):
  result = {}
  for token in token_stream:
    result[token] = result.get(token,0) + 1
  return result

def cosine_distance(freq1, freq2):
  numerator = sum(freq1.get(token,0) * freq2.get(token,0) for token in set(freq1).union(set(freq2)))
  denominator = sqrt(sum(v ** 2 for v in freq1.values())) * sqrt(sum( v ** 2 for v in freq2.values()))
  try:
    return 1.0 - (numerator / denominator)
  except ZeroDivisionError:
    return 1.0

def lower_clean(string):
  output = []
  for c in string:
    if c.isalnum():
      output += c.lower()
    else:
      output += ' '
  output = ' '.join(''.join(output).split())
  return output 
  

class NearestString(object):
  def __init__( self
              , strings
              , model   = bttgrams
              , metric  = cosine_distance
              , norm    = lower_clean
              ):
    self.metric = metric
    self.model = model
    self.norm = norm
    self.models = dict((s, frequencies(model(norm(s)))) for s in strings)
  
  def distances(self, string):
    instance = frequencies(self.model(self.norm(string)))
    distances = dict((s, self.metric(self.models[s],instance)) for s in self.models)
    return distances

  def __call__(self, string):
    distances = self.distances(string)
    nearest_neighbour = sorted(distances, key = distances.get)[0]
    return nearest_neighbour

if __name__ == "__main__":
  strings = [ "test string"
            , "exam string"
            , "hello world"
            ]
  classif = NearestString(strings)
  print "test ->",classif("test")
  print "examination ->",classif("examination")
    
